package com.acwing.partition29;

import java.io.*;

/**
 * @author `RKC`
 * @date 2022/3/11 15:16
 */
public class AC2875超级胶水_区间dp {

    private static final int N = 100010;
    private static int[] w = new int[N], s = new int[N];
    private static long[][] f;
    private static int n;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(reader.readLine());
        //TODO MLE、TLE，通过数据5/10
        f = new long[n + 1][n + 1];
        String[] ss = reader.readLine().split(" ");
        for (int i = 0; i < n; i++) w[i] = Integer.parseInt(ss[i]);
        for (int i = 1; i <= n; i++) s[i] = s[i - 1] + w[i - 1];
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                f[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    f[i][j] = Math.min(f[i][j], f[i][k] + f[k + 1][j] + (long) (s[k + 1] - s[i]) * (s[j + 1] - s[k + 1]));
                }
            }
        }
        writer.write(f[0][n - 1] + "\n");
        writer.flush();
    }
}
